package Matrix;

/**
 * 240.搜索二维矩阵||
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 * ● 每行的元素从左到右升序排列。
 * ● 每列的元素从上到下升序排列。
 */
public class searchMatrix {
    /**
     * hot100一刷
     */
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            for (int[] row : matrix) {
                int index = search(row, target);
                if (index >= 0) {
                    return true;
                }
            }
            return false;
        }

        public int search(int[] nums, int target) {
            int low = 0, high = nums.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                int num = nums[mid];
                if (num == target) {
                    return mid;
                } else if (num > target) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            return -1;
        }
    }


    /**
     * hot100二刷
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int top = 0;
        int right = matrix[0].length - 1;
        while (top < matrix.length && right >= 0) {
            if (matrix[top][right] == target) {
                return true;
            } else if (matrix[top][right] > target) {
                right--;
            } else {
                top++;
            }
        }
        return false;
    }


}
